package leetcode.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
 * <p>
 * 树的 最大宽度 是所有层中最大的 宽度 。
 * <p>
 * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
 * <p>
 * 题目数据保证答案将会在  32 位 带符号整数范围内。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,3,2,5,3,null,9]
 * 输出：4
 * 解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [1,3,2,5,null,null,9,6,null,7]
 * 输出：7
 * 解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
 * 示例 3：
 * <p>
 * <p>
 * 输入：root = [1,3,2,5]
 * 输出：2
 * 解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点的数目范围是 [1, 3000]
 * -100 <= Node.val <= 100
 */
public class LeetCode662_WidthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode[] tn = new TreeNode[3001];
        int[] w = new int[3001];

        int p = 0, q = 0;
        int k, m;
        tn[q++] = root;
        w[0] = 1;
        int r = 0;

        while (p != q) {
            k = p;
            m = q;
            p = q;

            // 标号为从根节点依次往下的递增值
            // 当前层最后一个节点标号与该层第一个的标号的差值 + 1
            r = Math.max(r, w[q - 1] - w[k] + 1);

            for (int i = k; i < m; i++) {
                TreeNode curNode = tn[i];
                int x = w[i];

                if (curNode.left != null) {
                    w[q] = x * 2;
                    tn[q++] = curNode.left;
                }
                if (curNode.right != null) {
                    w[q] = x * 2 + 1;
                    tn[q++] = curNode.right;
                }
            }
        }
        return r;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t3 = new TreeNode(1);
        TreeNode t2 = new TreeNode(1);
        TreeNode t5 = new TreeNode(1);
        TreeNode t33 = new TreeNode(1);
        TreeNode t9 = new TreeNode(1);

        t1.left = t3;
        t1.right = t2;
        t3.left = t5;
        t3.right = t33;
        t2.right = t9;

        int i = new LeetCode662_WidthOfBinaryTree().widthOfBinaryTree(t1);

    }
}
